#include "network.h"
#include <iostream>                  // for std::cout
#include <utility>                   // for std::pair
#include <algorithm>                 // for std::for_each
#include <fstream>
#include <vector>
#include "global.h"

#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>

#include <boost/generator_iterator.hpp>
#include <boost/lexical_cast.hpp>

using namespace boost;

typedef std::pair<int, int> Edge;
typedef graph_traits < Graph >::vertex_descriptor vertex_descriptor;
typedef graph_traits < Graph >::edge_descriptor edge_descriptor;
typedef graph_traits < Graph >::adjacency_iterator adj_iterator;
typedef graph_traits < Graph >::out_edge_iterator out_edge_iterator;
typedef graph_traits < Graph >::degree_size_type degree_size_type;
typedef graph_traits < Graph >::vertices_size_type vertices_size_type;
typedef property_map<Graph, vertex_index_t>::type IndexMap;

//typedef graph_traits < Graph2 >::vertex_descriptor vertex_descriptor2;
//typedef graph_traits < Graph2 >::edge_descriptor edge_descriptor2;


Network::Network():g(NULL), distanceMap(NULL), staleInformation(NULL)
{
}

Network::~Network()
{
    delete staleInformation;
    std::vector<int>* distanceCopy = NULL;

    int noOfVertices = num_vertices(*g);
    for (int i=0; i< noOfVertices; i++)
    {
        distanceCopy = distanceMap->find(i)->second;
        delete distanceCopy;
        distanceCopy = NULL;
    }

    delete distanceMap;
    delete g;
}

Network::Network(int noOfVertices, double density):g(NULL), distanceMap(NULL), staleInformation(NULL)
{
	//	noOfVertices = 5;
	//	density = 0.1;
	//	enum nodes { A, B, C, D, E };
	//	// below should be replaced by generating the edge array from
	//	// a random number generator based on the density parameter
	//	Edge edge_array[] = { Edge(A, E), Edge(A, C), Edge(B, D), Edge(B, E),
	//			Edge(C, B), Edge(C, D), Edge(D, E) };
	//	double weights[] = { 1, 1, 1, 1, 1, 1,  1};
	//	int num_arcs = sizeof(edge_array) / sizeof(Edge);
	//
	int numOfTies = density * (noOfVertices * (noOfVertices-1)/2);
	// int numOfTies = boost::lexical_cast<int>(numberOfTies);
	unsigned vertex1, vertex2;

	// as a degenerate case, you can set min = max for uniform_int
	boost::uniform_int<> uni_dist(1, noOfVertices);
	boost::variate_generator<base_generator_type&, boost::uniform_int<> > deg(generator, uni_dist);

	g = new Graph(noOfVertices);
	int loopCount = 0;
	int edgeCount = 0;
	while (edgeCount != numOfTies)
	{
		vertex1 = deg()-1;
		vertex2 = deg()-1;
		//cout << "random vertex1: " << vertex1 << "----random vertex2: " << vertex2 << endl;
		loopCount++;
		if (vertex1 == vertex2)
		{
			continue;
		}

		if (!isAdjacent(vertex1, vertex2))
		{
			add_edge(vertex1, vertex2, 1, *g);
			edgeCount++;
		}
	}

	distanceMap = new unorderedMap();
	staleInformation = new bool[noOfVertices];
	vector<int> *distanceList = NULL;
	for (int i=0; i<noOfVertices; i++)
	{
		staleInformation[i] = true;
		distanceList = new vector<int>(noOfVertices, 0); // initialise all elements to 0
		distanceMap->insert(std::make_pair(i, distanceList));
	}

	//cout << "edgeCount: " << edgeCount << "; loopCount: " << loopCount << endl;

	//	unsigned vertex1, vertex2;
	//	int edgeCount = 0;
	//	edge_descriptor e1, e2;
	//	bool added = false;
	//	Graph g1; // test graph of type "Graph2" to ensure duplicate edges are not present
	//	vector<Edge> randomEdges;
	//	vertex_descriptor vertx1;
	//	vertex_descriptor vertx2;
	//
	//	g1.clear();
	//	int loopCount = 0;
	//	while (edgeCount != numOfTies)
	//	{
	//		vertex1 = deg()-1;
	//		vertex2 = deg()-1;
	//		//cout << "random vertex1: " << vertex1 << "----random vertex2: " << vertex2 << endl;
	//		loopCount++;
	//		if (vertex1 == vertex2)
	//		{
	//			continue;
	//		}
	//
	//		vertx1 = vertex(vertex1, g1);
	//		vertx2 = vertex(vertex2, g1);
	//		tie (e1, added )= add_edge(vertx1, vertx2, g1);
	//
	//		IndexMap index = get(vertex_index, g1);
	//		out_edge_iterator e6, e7;
	//		tie(e6, e7) =  out_edges(vertx1, g1);
	//
	//		bool oneEncountered = false;
	//		bool atLeasttwoEncountered = false;
	//
	//		while (e6 != e7)
	//		{
	//			//cout << index [source(*e6, g1)] << endl;
	//			//cout << index [target(*e6, g1)] << endl;
	//			if (index [target(*e6, g1)] == vertex2)
	//			{
	//				if (oneEncountered)
	//				{
	//					//remove_edge(*(e6.first), g1);
	//					// remove_edge(vertex1, vertex2, g1);
	//					//cout << "Duplicate edge " << vertex1 << "--" << vertex2 << endl ;
	//					atLeasttwoEncountered = true;
	//				}
	//				else
	//				{
	//					oneEncountered = true;
	//				}
	//			}
	//			e6++;
	//		}
	//
	//		if(!atLeasttwoEncountered)
	//		{
	//			randomEdges.push_back(Edge(vertex1, vertex2));
	//			edgeCount++;
	//		}
	//	}
	//
	//	// set all weights to be 1
	//	int *weights = new int[edgeCount];
	//	for (int j=0; j<edgeCount; j++)
	//	{
	//		weights[j] = 1;
	//	}
	//
	//	cout << "randomEdges: " << randomEdges.size() << "; loopCount: " << loopCount << endl;
	//	g = new Graph(randomEdges.begin(), randomEdges.end(), weights, noOfVertices);
	//	if (g == NULL)
	//	{
	//		cout << "Error in memory allocation\n" ;
	//		exit(0);
	//	}
}

//
//	Actor *indexedActor = NULL;
//	for (int i=0; i < noOfVertices; i++)
//	{
//		indexedActor = new Actor(i+1, this);
//		actorList.push_back(indexedActor);
//	}


// - not needed now as
Network::Network(const Network& ntwk) : g(NULL), distanceMap(NULL), staleInformation(NULL)
{
	//cout << "IN COPY CONSTRUCTOR" << endl;
	vector<int>* tempList = NULL;
	vector<int> *distanceList = NULL;

	g = new Graph(ntwk.getGraph());

	int noOfVertices = num_vertices(*g);
	const bool *staleInfoList = ntwk.getStaleInformationList();
	staleInformation = new bool[noOfVertices];
	copy (staleInfoList, staleInfoList+noOfVertices, staleInformation);

	distanceMap = new unorderedMap();
	const unorderedMap* distMap = ntwk.getUnorderedMap();

	for (int i=0; i<noOfVertices; i++)
	{
		tempList =  distMap->find(i)->second;
		distanceList = new vector<int>(noOfVertices, 0); // initialise all elements to 0
		copy (tempList->begin(), tempList->end(), distanceList->begin());

		//cout << "distanceList Contents" << " are : ";
		/*std::vector<int>::iterator it;
		for (it=distanceList->begin(); it != distanceList->end(); it++)
		{
			cout << *it << ", ";
		}
		cout << endl;

		cout << "tempList Contents are : ";
		for (it=tempList->begin(); it != tempList->end(); it++)
		{
			cout << *it << ", ";
		}
		cout << endl;*/

		distanceMap->insert(std::make_pair(i, distanceList));
	}
	/*	vector<Actor*> toBeCopied = ntwk.getActors();
	Actor *newActor = NULL;

	std::vector<Actor* >::iterator it;
	for (it=toBeCopied.begin(); it != toBeCopied.end(); it++)
	{
		if (*it)
		{
			newActor = new Actor((*(*it)));
			actorList.push_back(newActor);
		}
	}*/
}

int Network::getNumEdgesOnGeodesic( int srcNode, int destNode ) const
{
	//int numOfHopsToDest = -1;
	//char name[] = "ABCDE";

	//	// conversion from 1-based indexing to 0-based indexing
	//	srcNode = srcNode - 1;
	//	destNode = destNode - 1;

	property_map<Graph, edge_weight_t>::type weightmap = get(edge_weight, *g);

	std::vector<int>* distanceCopy = distanceMap->find(srcNode)->second;
	if (staleInformation[srcNode])
	{
		//cout << "CALLING DIJSKTRA ALGORITHM" << endl;
		std::vector<vertex_descriptor> p(num_vertices(*g));
		std::vector<int> d(num_vertices(*g));
		vertex_descriptor s = vertex(srcNode, *g);
		dijkstra_shortest_paths(*g, s, predecessor_map(&p[0]).distance_map(&d[0]));

		/*cout << "Current Contents for Node " << srcNode << "is : ";
		std::vector<int>::iterator it;
		for (it=distanceCopy->begin(); it != distanceCopy->end(); it++)
		{
			cout << *it << ", ";
		}
		cout << endl;*/

		copy (d.begin(), d.end(), distanceCopy->begin());
		staleInformation[srcNode] = false;
	/*	cout << "Modified Contents for Node " << srcNode << "is : ";
		for (it=distanceCopy->begin(); it != distanceCopy->end(); it++)
		{
			cout << *it << ", ";
		}
		cout << endl;*/

		//update the entry in hashmap
		return d[(unsigned)destNode];
	}
	else
	{
	//	cout << "NOT CALLING DIJSKTRA ALGORITHM" << endl;
		return (*distanceCopy)[(unsigned)destNode];
	}
	//std::cout << "distances and parents:" << std::endl;
	//	graph_traits < Graph >::vertex_iterator vi, vend;
	//	for (tie(vi, vend) = vertices(*g); vi != vend; ++vi)
	//	{
	//		//std::cout << "distance(" << "V_" << (*vi) << ") = " << d[*vi] << ", ";
	//		//std::cout << "parent(" << "V_" << (*vi) << ") = " << "V_" << (p[*vi]) << std::endl;
	//		if (*vi == (unsigned)destNode)
	//		{
	//			numOfHopsToDest = d[*vi];
	//		}
	//	}
	//	std::cout << std::endl;
}

// adds an edge between 'src' and 'dest' nodes
void Network::add( int src, int dest )
{
	//	// conversion from 1-based indexing to 0-based indexing
	//	src = src-1;
	//	dest = dest-1;
	// Edge e(src, dest);
	//int weight = 1;
	add_edge(src, dest, 1, *g);
	int noOfVertices = num_vertices(*g);
	for (int i=0; i<noOfVertices ;i++)
	{
		staleInformation[i] = true;
	}
}

// deletes/removes the edge between 'src' and 'dest' nodes
// NOTE: 'delete' is a keyword in C++. So, could not use that for method name.
void Network::remove( int src, int dest )
{
	//	// conversion from 1-based indexing to 0-based indexing
	//	src = src-1;
	//	dest = dest-1;
	//Edge e(src, dest);
	remove_edge(src, dest, *g);
	int noOfVertices = num_vertices(*g);
	for (int i=0; i< noOfVertices;i++)
	{
		staleInformation[i] = true;
	}
}

bool Network::isAdjacent( int src, int dest )
{
	//	src = src-1;
	//	dest = dest-1;
	vertex_descriptor u = vertex(src, *g);
	adj_iterator adjStart, adjEnd;

	for (tie(adjStart, adjEnd) = adjacent_vertices(u, *g); adjStart != adjEnd; ++adjStart)
	{
		//cout << " *adjStart = " << *adjStart << endl;
		if (*adjStart == (unsigned)dest) {
			return true;
		}
	}
	return false;
}

void Network::dumpNetwork( const char* fileName )
{
	ofstream outputFile;
	outputFile.open(fileName);// opens the file

	outputFile << "graph ourgraph {" << endl;
	string vertexTemplate = "V_";

	graph_traits<Graph>::edge_iterator ei, ei_end;
	IndexMap index = get(vertex_index, *g);

	for (tie(ei, ei_end) = edges(*g); ei != ei_end; ++ei)
	{
		outputFile << vertexTemplate << (index[source(*ei, *g)]+1)
		<< " -- " << vertexTemplate << (index[target(*ei, *g)]+1) << ";" << endl;
	}
	outputFile << "}"<< endl;
	outputFile.close();
}

// returns the actors in the network - not needed now as Srinath and Subbu decided
//const vector<Actor*>& Network::getActors() const
//{
//	// returns the actors vector as a const object.
//	return actorList;
//}

//double Network::getUtility()
//{
//	double totalUtilityOfAllActors = 0.0;
//	std::vector<Actor* >::iterator it;
//	for (it=actorList.begin(); it != actorList.end(); it++)
//	{
//		if (*it)
//		{
//			totalUtilityOfAllActors += (*it)->getUtility(this);
//		}
//	}
//	return totalUtilityOfAllActors;
//}


const Graph& Network::getGraph() const
{
	return *g;
}

const bool* Network::getStaleInformationList()const
{
	return staleInformation;
}

const unorderedMap* Network::getUnorderedMap()const
{
	return distanceMap;
}

NTWK_STRUCT Network::getNetworkStructure(ofstream *ofile)
{
	// Star, Complete, Null, Shared Graphs
	const int NO_OF_COMPARING_GRAPHS = 4;
	double nearNessIndex[NO_OF_COMPARING_GRAPHS] = {0, 0, 0, 0};

		vector<degree_size_type> sortedInOutDegree;
		degree_size_type degree;
		vertex_descriptor u;

		graph_traits < Graph >::vertex_iterator vi, vend;
		for (tie(vi, vend) = vertices(*g); vi != vend; ++vi)
		{
			u = vertex(*vi, *g);
			degree = out_degree(u, *g);
			sortedInOutDegree.push_back(degree);
		}

		std::sort(sortedInOutDegree.begin(), sortedInOutDegree.end());
		reverse(sortedInOutDegree.begin(),sortedInOutDegree.end());

		int noofVertices = (int)num_vertices(*g);

		bool firstElement = true;
		int curDegree;
		// Dump the vector to check the result
		for (vector<degree_size_type>::const_iterator citer = sortedInOutDegree.begin();
		citer != sortedInOutDegree.end(); ++citer)
		{
			curDegree = (unsigned)(*citer);
			nearNessIndex[NS_NULL] += SQR(curDegree - 0); // pow(curDegree - 0, 2.0); // null
                	if (ofile)
			{
			   *ofile << (*citer) << ", ";
			}
			else
			{
			   cout << (*citer) << ", ";
			}

			if (firstElement)
			{
				// cout << (*citer) << endl;
				nearNessIndex[NS_STAR] += SQR(curDegree -(noofVertices-1)); // pow((curDegree -(noofVertices-1)),2); // star
				firstElement = false;
			}
			else
			{
				nearNessIndex[NS_STAR] += SQR(curDegree - 1); //pow(curDegree - 1, 2); // star
			}
			nearNessIndex[NS_SHARED] += SQR(curDegree - 2); //pow(curDegree - 2, 2);// shared
			nearNessIndex[NS_COMPLETE] += SQR(curDegree - (noofVertices-1)); // pow(curDegree - (noofVertices-1), 2); // complete
		}
                if (ofile)
		{
		   *ofile << endl;
		}
		else
		{
		   cout << endl;
		}
		// cout << nearNessIndex[NS_NULL] << " " << nearNessIndex[NS_STAR] << " " << nearNessIndex[NS_SHARED] << " " << nearNessIndex[NS_COMPLETE]
		// <<endl;

		int minGraph = ( min_element(nearNessIndex, nearNessIndex + NO_OF_COMPARING_GRAPHS) - nearNessIndex);
		NTWK_STRUCT result;
		switch(minGraph)
		{
			case NS_NULL:
				if (nearNessIndex[NS_NULL] == 0.0)
				{
					result = NS_NULL;
				}
				else
				{
					result = NS_NEAR_NULL;
				}
				break;
			case NS_STAR:
				if (nearNessIndex[NS_STAR] == 0.0)
				{
					result = NS_STAR;
				}
				else
				{
					result = NS_NEAR_STAR;
				}
				break;
			case NS_SHARED:
				if (nearNessIndex[NS_SHARED] == 0.0)
				{
					result = NS_SHARED;
				}
				else
				{
					result = NS_NEAR_SHARED;
				}
				break;
			case NS_COMPLETE:
				if (nearNessIndex[NS_COMPLETE] == 0.0)
				{
					result = NS_COMPLETE;
				}
				else
				{
					result = NS_NEAR_COMPLETE;
				}
				break;
			default:
				result = NS_TYPE_SIZE;
		}
		// cout << "Min graph" << result << endl;
		return result;
}


